In general, in fields which require security, a method based on a secret, which is shared with an encryptor, is adopted as means for certifying one's own authenticity.
For example, in IC cards, etc., which are used for electronic settlement, an individualized ID and secret information are stored in an IC in the card, and the IC card has a cipher processing function for executing authentication based on the ID and secret information. In another example, there is means for certifying authenticity of an SD (trademark) card in copyright protection of contents.
In each of the above examples, it is necessary that an authenticatee include a secret key and an encryptor. However, the implementation of an encryptor requires a relatively large circuit scale. Thus, in an environment in which restrictions to the circuit scale are imposed at the same time, it is very difficult to certify one's own authenticity. A typical example, in which restrictions to the circuit scale are imposed, is RFID (Radio Frequency Identification). Thus, in recent years, there is a background that the need on implementation is increasing.